#ifndef _Ape__Collections_LinkedList_h
#define _Ape__Collections_LinkedList_h

#include <Ape/Object.h>
#include <Ape/Collections/CollectionHelpers.h>

namespace Ape {
	namespace Collections {
		struct LL_Joint {
			LL_Joint* Next;
			LL_Joint* Prev;
			
			void* Value;
			
			static LL_Joint* Create();
		};
		
		class LinkedList_Impl : public Object {
			TYPE_NAME ("Ape::Collections::LinkedList_Impl")
		protected:
			LL_Joint* m_First;
			LL_Joint* m_Last;
			size_t m_Count;
			
			LinkedList_Impl();
			virtual ~LinkedList_Impl();
			
			void _Append (void* value);
			void _Prepend (void* value);
			void* _FetchFirst();
			void* _FetchLast();
			
			void InitFirstValue (void* value);
			
			void DisposeValues();
			virtual void DisposeValue (void* value) = 0;
		public:
			size_t get_Count() const;
			
			LL_Joint* _GetFirstJoint() const;
		};
		
		template <typename E_t>
		class LinkedListIterator;
		
		template <typename E_t>
		class LinkedList : public LinkedList_Impl {
			TYPE_NAME ("Ape::Collections::LinkedList<E_t>")
		public:
			typedef LinkedListIterator<E_t> Iterator_t;
			typedef LinkedList<E_t> Container_t;
			
			LinkedList();
			virtual ~LinkedList();
			
			void Append (const E_t& v);
			void Prepend (const E_t& v);
			E_t FetchFirst();
			E_t FetchLast();
			
			void Clear();
			
			virtual void DisposeValue (void* value);
		};
		
		template<typename E_t>
		LinkedList<E_t>& operator << (LinkedList<E_t>& list, const E_t& value);
		
		template<typename E_t>
		LinkedList<E_t>& operator >> (LinkedList<E_t>& list, E_t& value);
		
		template<typename E_t>
		E_t& operator << (E_t& value, LinkedList<E_t>& list);
		
		
		// -------------------------------------------
		template <typename E_t>
		LinkedList<E_t>::LinkedList() {}
		
		template <typename E_t>
		LinkedList<E_t>::~LinkedList() {
			DisposeValues();
		}
		
		template <typename E_t>
		void LinkedList<E_t>::Clear() {
			DisposeValues();
		}
		
		template <typename E_t>
		void LinkedList<E_t>::Append (const E_t& v) {
			void* p = TypedHelper<E_t>::ToHeap (v);
			_Append (p);
		}
		template <typename E_t>
		void LinkedList<E_t>::Prepend (const E_t& v) {
			void* p = TypedHelper<E_t>::ToHeap (v);
			_Prepend (p);
		}
		
		template <typename E_t>
		E_t LinkedList<E_t>::FetchFirst() {
			void* p = _FetchFirst();
			E_t v = TypedHelper<E_t>::ToStack (p);
			TypedHelper<E_t>::Free (p);
			return v;
		}
		template <typename E_t>
		E_t LinkedList<E_t>::FetchLast() {
			void* p = _FetchLast();
			E_t v = TypedHelper<E_t>::ToStack (p);
			TypedHelper<E_t>::Free (p);
			return v;
		}
		
		template <typename E_t>
		void LinkedList<E_t>::DisposeValue (void* value) {
			TypedHelper<E_t>::Free (value);
		}
		
		template<typename E_t>
		LinkedList<E_t>& operator << (LinkedList<E_t>& list, const E_t& value) {
			list.Append (value);
			return list;
		}
		
		template<typename E_t>
		LinkedList<E_t>& operator >> (LinkedList<E_t>& list, E_t& value) {
			value = list.FetchFirst();
			return list;
		}
		
		template<typename E_t>
		E_t& operator << (E_t& value, LinkedList<E_t>& list) {
			value = list.FetchFirst();
			return value;
		}
		
		
		template <typename E_t>
		class LinkedListIterator : public Object {
			TYPE_NAME ("Ape::Collections::LinkedListIterator<E_t>")
		private:
			const LinkedList<E_t>& m_List;
			LL_Joint* m_CurrentJoint;
		public:
			LinkedListIterator (const LinkedList<E_t>& array);
			LinkedListIterator (const LinkedListIterator<E_t>& other);
			virtual ~LinkedListIterator();
			
			operator const E_t () const;
			
			LinkedListIterator<E_t>& operator ++ ();
			LinkedListIterator<E_t> operator ++ (int /*unused*/);
			
			bool Continue() const;
			
			//virtual const String ToString() const;
		};
		
		template <typename E_t>
		LinkedListIterator<E_t>::LinkedListIterator (const LinkedList<E_t>& list)
				: m_List (list),
				m_CurrentJoint (list._GetFirstJoint() )
		{}
		
		template <typename E_t>
		LinkedListIterator<E_t>::LinkedListIterator (const LinkedListIterator<E_t>& other)
				: Object (other),
				m_List (other.m_List),
				m_CurrentJoint (other.m_CurrentJoint)
		{}
		
		template <typename E_t>
		LinkedListIterator<E_t>::~LinkedListIterator() {}
		
		template <typename E_t>
		bool LinkedListIterator<E_t>::Continue() const {
			return m_CurrentJoint != NULL;
		}
		
		template <typename E_t>
		LinkedListIterator<E_t>::operator const E_t () const {
			return TypedHelper<E_t>::RefToStack (m_CurrentJoint->Value);
		}
		
		template <typename E_t>
		LinkedListIterator<E_t>& LinkedListIterator<E_t>::operator ++ () {
			if (m_CurrentJoint)
				m_CurrentJoint = m_CurrentJoint->Next;
			return *this;
		}
		
		template <typename E_t>
		LinkedListIterator<E_t> LinkedListIterator<E_t>::operator ++ (int /*unused*/) {
			LinkedListIterator<E_t> copy (*this);
			if (m_CurrentJoint)
				m_CurrentJoint = m_CurrentJoint->Next;
			return copy;
		}
		
	}
}

#endif // _Ape__Collections_LinkedList_h
